# 给定两个长度都为N的数组weights和values，weights[i]和values[i]分别代表 i号物品的重量和价值。
# 给定一个正数bag，表示一个载重bag的袋子，你装的物品不能超过这个重量。返回你能装下最多的价值是多少？


def max_value(weights: list, values: list, bag: int):

    return process(weights, values, bag, 0)
    # return process1(weights, values, 0, 0, bag, 0)


def process(weights: list, values: list, res: int, k: int):
    """
    k 号物品之后的最大价值
    """
    if k == len(weights):
        return 0

    # 不要当前物品
    v1 = process(weights, values, res, k+1)
    # 只有当 res >= 当前物品重量时，才能要当前物品
    v2 = values[k] + process(weights, values, res-weights[k], k+1) if res >= weights[k] else 0
    return max(v1, v2)


def process_wrong(weights: list, values: list, res: int, k: int):
    """
    错误写法
    """
    if k == len(weights) or res < 0:
        return 0
    #                                                   这里先放入物品，在考虑之后的重量，是错误的
    return max(process_wrong(weights, values, res, k+1),values[k] + process_wrong(weights, values, res-weights[k], k+1))


def process1(weights: list, values: list, already_weight: int, already_value: int, bag: int, k: int):
    if already_weight > bag:
        return 0
    if k == len(weights):
        return already_value

    return max(process1(weights, values, already_weight, already_value, bag, k+1),
               process1(weights, values, already_weight+weights[k], already_value+values[k], bag, k+1))


if __name__ == "__main__":
    weights = [3, 2, 4, 7]
    values = [5, 6, 3, 19]
    bag = 11
    print(max_value(weights, values, bag))
